﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphLibrary.Algorithms
{
    sealed public class DijkstraAlgorithm<TVertex, TEdge> : GraphAlgorithm<TVertex, TEdge>
        where TEdge : IEdge<TVertex>
    {
        Dictionary<TVertex, int> _vertex_ind = new Dictionary<TVertex, int>();

        //массив с минимальными расстояниями
        //до всех вершин графа из исходной вершины
        Dictionary<TVertex, double> _distances = new Dictionary<TVertex, double>();
        //массив, служащий для имитации каймы на основе массива dist
        Dictionary<TVertex, bool> _visited = new Dictionary<TVertex, bool>();

        Stack<TVertex> _path = new Stack<TVertex>();

        public Stack<TVertex> Path
        {
            get
            {
                return _path;
            }
        }

        private Func<TEdge, double> _weight;

        public double _distance;

        public double Distance { get { return _distance; } }

        double[,] _agencyMatrix;

        public DijkstraAlgorithm(IGraph<TVertex, TEdge> graph, Func<TEdge, double> weight)
        {
            Graph = graph;
            _weight = weight;
        }

        public void Execute(TVertex source, TVertex target)
        {
            _agencyMatrix = Graph.ToAgencyMatrix(_weight);
            int k = 0;
            foreach (TVertex v in Graph.Vertices)
            {
                _vertex_ind.Add(v, k++);
            }
            foreach (TVertex v in Graph.Vertices)
            {
                _distances.Add(v, int.MaxValue);
                _visited.Add(v, false);
            }
            _distances[source] = 0;
            _visited[source] = true;
            TVertex cur = source;
            do
            {
                cur = FindVertexWithMinDist(cur);
                _visited[cur] = true;
            }
            while (!cur.Equals(target));
            PathToStack(source, target);
            _distance = _distances[target];
        }

        private void PathToStack(TVertex source, TVertex target)
        {
            TVertex v1 = target;
            while (!target.Equals(source))
            {
                _path.Push(target);
                foreach (TVertex v in Graph.Vertices)
                {
                    if ((_distances[target] == _distances[v] + _agencyMatrix[_vertex_ind[v], _vertex_ind[target]]) && (!v.Equals(target)))
                    {
                        v1 = v;
                        break;
                    }
                }
                target = v1;
            }
            _path.Push(target);
        }

        private TVertex FindVertexWithMinDist(TVertex cur)
        {
            double MinDist = double.MaxValue;
            TVertex tmp = cur;
            foreach (TVertex v in _visited.Keys)
            {
                if (!_visited[v])
                {
                    if (_agencyMatrix[_vertex_ind[cur], _vertex_ind[v]] == 0)
                        _agencyMatrix[_vertex_ind[cur], _vertex_ind[v]] = int.MaxValue;
                    _distances[v] = Math.Min(_distances[v], Math.Abs(_distances[cur] + _agencyMatrix[_vertex_ind[cur], _vertex_ind[v]]));
                    if (_distances[v] < MinDist)
                    {
                        MinDist = _distances[v];
                        tmp = v;
                    }
                }
            }
            return tmp;
        }
    }
}
